package pers.tz.题目.leetcode.链表;

import pers.tz.common.ListNode;
import pers.tz.common.ListUtils;

/**
 * 实习有赞挂
 *
 * @author irony
 * @date 2024-03-11
 */
public class leetcode_0019_删除链表的倒数第N个节点 {
//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//
// 示例 1：
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
//
// 示例 2：
//输入：head = [1], n = 1
//输出：[]
//
// 提示：
// 链表中结点的数目为 sz
// 1 <= sz <= 30
// 0 <= Node.val <= 100
// 1 <= n <= sz
//
// 进阶：你能尝试使用一趟扫描实现吗？

    public static void main(String[] args) {
        ListNode head = ListUtils.generateList(3);
        ListUtils.printList(head);

        head = removeNthFromEnd(head, 4);
        ListUtils.printList(head);
    }

    // 双指针
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = null; // 标注要删除的节点
        ListNode cur = head;
        while (cur != null) {
            n--;

            // 落后N+1个
            if (n == -1) {
                pre = head;
            }
            // 前移
            if (n < -1) {
                pre = pre.next;
            }
            cur = cur.next;
        }

        // 边界条件，倒数等于列表长度，删除头节点
        if (n == 0) {
            return head.next;
        }

        // 边界条件，倒数比列表长（原题中保证不会超过列表长度）

        // 删除
        pre.next = pre.next.next;
        return head;
    }
}
